



#ifndef _C_GRAPH____H_
#define _C_GRAPH____H_  


#include"stl_list.h"



#define Vex_str_len 16 // 32
#define Arc_str_len 16 // 32

typedef struct  __vertex_
{
	char str[Vex_str_len];   // 描述字符串
	float value;    // 顶点权值
	int sign;       // 遍历的时候会有标记。

	List inArc;     // 进该节点的边(弧) 列表，链表数据的headvex是自己。链表的 datapoint = (Arc*) ,
	List outArc;    // 出该节点的边     列表，链表数据的tailvex是自己。链表的 datapoint = (Arc*) ,

	ListNode* vex_list_node;  // 在图的顶点链表里的节点。在移除顶点的时候使用。

	// 和下面边的一样，删除vex_list_node的时候不能调用list_remove 删除。而是自己重写删除的代码。
}Vertex;

typedef struct  __arc_
{
	char str[Arc_str_len];   // 描述字符串
	float value;    // 边的权值
	int sign;       // 遍历的时候会有标记。

	ListNode* inArcNode;  // 这条边在headvex 的inArc的链表中的节点。在删除边的时候用得到。
	ListNode* outArcNode; // 这条边在tailvex 的outArc的链表中的节点。在删除边的时候用得到

	// 重点警告：这里单链表的remove函数，会破坏outArcNode，inArcNode与弧节点的对应关系！因此删除弧节点不能直接调用remove！否则会出错。 

	Vertex* headvex;	//头节点,尾  ---- >>>>  头	
	Vertex* tailvex;    //尾节点,尾  ---- >>>>  头

	ListNode* arc_list_node;  // 在图的边链表里的节点。在移除边的时候使用。

}Arc;



typedef struct _Graph__ {	//
	List vertex_list;	         // 所有结点的列表，列表的 datapoint 是 （Vertex*）
	List arc_list;               // 所有边的链表。链表的 datapoint 是 (Arc*)  
	bool is_directed_graph;      // 是否有向图。有向图无向图的存储结构是一样的，如果是无向图，搜索的时候，入边可以当出边参与算法搜索。
}Graph;

  
// 绘制图
void draw_graph(Graph* graph);
// 打印图
void print_graph(Graph* graph);



/// <summary>
/// 寻找图中顶点值对应的顶点。
/// </summary>
/// <param name="graph">图</param>
/// <param name="vex_data">顶点的值</param>
/// <returns>顶点指针</returns>
Vertex* Graph_find_vertex(Graph* graph, float vex_data);

/// <summary>
/// 图中插入一条边，如果是有向图，边的方向是 尾 ---->> 头
/// </summary>
/// <param name="graph">图</param>
/// <param name="arc">边结构体</param>
/// <param name="tailvertex">尾节点</param>
/// <param name="headvertex">头节点</param>
void Graph_ins_arc(Graph* graph, Arc* arc, Vertex* tailvertex, Vertex* headvertex);


/// <summary>
/// 插入顶点，新插入的顶点没有边。
/// </summary>
/// <param name="graph">图</param>
/// <param name="vertex">顶点</param>
void Graph_ins_vertex(Graph* graph, Vertex* vertex);

/// <summary>
/// 移除边，移除边会找到边的头尾节点，分别删除两个节点的入边和出边。
/// </summary>
/// <param name="graph">图</param>
/// <param name="arc">边</param>
void Graph_remove_arc(Graph* graph, Arc* arc);

/// <summary>
/// 移除顶点，移除顶点会移除与该顶点相关的边
/// </summary>
/// <param name="graph">图</param>
/// <param name="vertex">顶点</param>
void Graph_remove_vertex(Graph* graph, Vertex* vertex);

/// <summary>
/// 初始化图
/// </summary>
/// <param name="graph">图</param>
/// <param name="is_directed_graph">是否有向图</param>
void Graph_init(Graph* graph, bool is_directed_graph);

/// <summary>
/// 销毁图，会删除所有顶点和边
/// </summary>
/// <param name="graph">图</param>
void Graph_destroy(Graph* graph);
//

//////////////  下面是图的算法，两个最小生成树算法，两个最短路径算法（现实一个） /////////////////////////////////////////////////


int arc_compare(Arc* arc1, Arc* arc2);

/// <summary>
/// Kruskal算法实现最小生成树。
/// 这个函数会将图看作是无向图
/// </summary>
/// <param name="graph">图</param>
/// <param name="min_tree">这个链表要空的（函数里会初始化），链表的datap是 Arc的指针，根据边的描述可以确定一个图</param>
void Graph_MinTree_Kruskal(Graph* graph, List* min_tree);


// 边，顶点都保存到链表里，遍历图直接在链表里遍历就行了，没必要进行深度优先或者广度优先遍历，反正都不确定……



//#include"sl_matrix.h"   // 这里一取消，就报大错。……
#define NO_Adjacent  9999 // 边的权重大于这个值，表示不相邻
/// <summary>
/// Dijkstra算法实现最短路径。这里要保证边的权值都是正的。
/// 如果边有负权值，可能会得不到正确的路径。
/// 最短路径的算法，用邻接矩阵来计算效率比较高，如果用邻接表，算法太复杂。
/// </summary>
/// <param name="m">图的临界矩阵，data[i][j] 表示i节点到j节点的边的权值，值大于9999表示不连通</param>
/// <param name="path">path.data[i]表示从源点到顶点i之间最短路径的前驱结点</param>
/// <param name="dist">dist.data[i]表示从源点到顶点i的最短路径长度</param>
/// <param name="start_index">源点的索引</param>
/// <returns></returns>
//int Graph_mat_MinWay_Dijkstra(mat m, ivec path, vec dist, int start_index);

/// <summary>
/// 拓扑排序
/// </summary>
/// <param name="graph">有向图</param>
/// <param name="topo">这个链表要空的（函数里会初始化）。datap是顶点指针，输出拓扑排序的顶点顺序（不唯一）</param>
/// <returns>如果有回路，拓扑排序失败</returns>
bool Graph_TopoSort(Graph* graph, List* topo);

//////////////      /////////////////////////////////////////////////////////////////////////////////////////////////









/// <summary>
/// 从 "D:\\graph.txt" 提取图的数据信息。
/// 数据格式： 尾节点值 头节点值 边表值
/// 
/// </summary>
/// <param name="str">字符串数组</param>
/// <param name="str_capacity">字符串最大容量</param>
/// <returns>字符串长度，不会超出字符串最大容量，返回-1表示没找到图的文件</returns>
int get_graph_string(char* str, int str_capacity);


void test_dgraph(void);

void test_ui_graph(void);

//测试最小生成树
void test_graph_min_tree(void);


//测试最短路径算法
void test_graph_dij(void);

void test_topo(void);






#endif





